We consider the problem of computing shortest paths having curvature at most one almost everywhere and visiting a sequence of $n$ points in the plane in a given order. This problem arises naturally in path planning for point car-like robots in the presence of polygonal obstacles, and is also a sub-problem of the Dubins Traveling Salesman Problem. This problem reduces to minimizing the function $F:\R^n\rightarrow\R$ that maps $(\theta_1,\ldots,\theta_n)$ to the length of a shortest curvature-constrained path that visits the points $p_1, \ldots, p_n$ in order and whose tangent in $p_i$ makes an angle $\theta_i$ with the $x$-axis. We show that when consecutive points are distance at least $4$ apart, all minima of $F$ are realized over at most $2^k$ disjoint convex polyhedra over which $F$ is strictly convex; each polyhedron is defined by $4n-1$ linear inequalities and $k$ denotes, informally, the number of $p_i$ such that the angle $\angle(p_{i-1},p_i,p_{i+1})$ is small. A curvature-constrained shortest path visiting a sequence points can therefore be approximated by standard convex optimization methods, which presents an interesting alternative to the known polynomial-time algorithms that can only compute a multiplicative constant factor approximation. Our technique also opens new perspectives for bounded-curvature path planning among polygonal obstacles. In particular, we show that, under certain conditions, if the sequence of points where a shortest path touches the obstacles is known then ``connecting the dots'' reduces to a family of convex optimization problems.

EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 003257 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 003257 | SxmlIndent | more

{{Explor lien
   |wiki=    Wicri/Lorraine
   |area=    InforLorV4
   |flux=    Main
   |étape=   Exploration
   |type=    RBID
   |clé=     Hal:inria-00539957
   |texte=   Bounded-Curvature Shortest Paths through a Sequence of Points
}}